/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mirac
 * Date: 2025-09-07
 * Time: 22:41
 */
public class HashBuck {

    static class Node {
        public int key;
        public int val;
        public Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    public Node[] array = new Node[10];
    public int userSize;

    public static final double DEFAULT_LOAD_FACTOR = 0.75f;

    public void putFirst(int key,int val) {
        int index = key % array.length;
        //根据key找的key所在的桶
        Node cur = array[index];
        //判断桶内是是否有key，有的话就更新val
        while (cur != null) {
            if (cur.key == key) {
                cur.val = val;
                return;
            }
            cur = cur.next;
        }
        //如果没有当前链表中，将key头插到桶中的链表中
        Node node = new Node(key,val);
        node.next = array[index];
        array[index] = node;
        userSize++;
        //判断当前负载因子是否大于等于0.75，大于就扩容
        if (doLoadFactor() >= DEFAULT_LOAD_FACTOR) {
            reSize();
        }
    }

    //求负载因子
    private double doLoadFactor() {
        return userSize*1.0/array.length;
    }

    //进行扩容
    private void reSize() {
        //并不能简单的扩容，还需要将原来的每个key分配到新的桶中
        Node[] ret = new Node[2*array.length];
        //开始遍历每个桶
        for (int i = 0; i < array.length; i++) {
            //遍历每个桶内
            Node cur = array[i];
            while (cur != null) {
                //计算这个节点新的桶
                int newIndex = cur.key % ret.length;
                //记录原节点的下一个节点
                Node curN = cur.next;
                //把这个结点放到新的桶里面
                cur.next = ret[newIndex];
                ret[newIndex] = cur;

                //cur返回原来桶中继续遍历
                cur = curN;
            }
        }

        array = ret;
    }

    public int getVal(int key) {
        int index = key % array.length;
        Node cur = array[index];
        while (cur != null) {
            if (cur.key == key) {
                return cur.val;
            }
            cur = cur.next;
        }
        //找不到就返回-1
        return -1;
    }
}
